#!/usr/bin/python
#-*- coding:utf-8 -*-
# Description:  <C程序设计竞赛实训教程> 刘高军、何丽 编著 第11.2节：迷宫问题
#          0代表通路， 1代表墙，找到穿越迷宫的一条路径
#          

import numpy as np
from pprint import pprint
from collections import deque

path = deque()
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def seek(p, m, mark):
    x, y = p
    mark[p] = True
    if x == m.shape[0] - 2 and y == m.shape[1] - 2:
        return True
    for i, j in move:
        new_x, new_y = x + i, y + j
        if m[new_x][new_y]==0 and not mark[new_x][new_y] :
            if seek( (new_x, new_y), m, mark ):
                path.append( (new_x, new_y) )
                return True
    return False
        
    
def search(maze) :
    col = np.ones((maze.shape[0], 1), dtype=int)
    m = np.hstack([col, maze, col])
    row = np.ones((1, m.shape[1]), dtype=int)
    m = np.vstack([row, m, row])
    mark = np.zeros_like(m, dtype=bool)
    if seek((1,1), m, mark):
        path.append( (1,1) )
        print list(reversed(path))
        
if __name__ == '__main__':
    maze = np.array([
        [0, 0, 1, 0, 0, 0, 1, 1,],
        [1, 0, 0, 0, 1, 0, 0, 0,],
        [0, 0, 0, 1, 1, 0, 1, 1,],
        [1, 1, 0, 1, 0, 0, 0, 0,],
        [0, 0, 0, 0, 0, 1, 0, 1,],
        [1, 0, 1, 0, 0, 0, 0, 0,],
    ], dtype=int)

    pprint(maze)
    search(maze)
